package com.xk._02算法篇._03graph.graph;

import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * @description:
 * @author: xu
 * @date: 2022/10/5 20:20
 */
public abstract class Graph<V, E> {
    protected WeightManager<E> weightManager;
    public Graph(WeightManager<E> weightManager) {
        this.weightManager = weightManager;
    }
    public Graph() {}

    //获取顶点、边的数量
    public abstract int edgesSize();
    public abstract int verticsSize();

    //添加新的顶点、边
    public abstract void addVertex(V v);
    public abstract void addEdge(V from, V to);
    public abstract void addEdge(V from, V to, E weight);

    //删除顶点、边
    public abstract void removeVertex(V v);
    public abstract void removeEdge(V from, V to);

    //遍历图：
    //bfs：广度优先遍历；dfs：深度优先遍历
    public abstract void bfs(V begin, VertexVisitor<V> visitor);
    public abstract void dfs(V begin, VertexVisitor<V> visitor);
    public abstract void dfs1(V begin, VertexVisitor<V> visitor);

    //拓扑排序：卡恩算法
    public abstract List<V> topologicalSort();

    //最小生成树
    //prim：普利姆算法
    //kruskal：克鲁斯卡尔算法
    public abstract Set<EdgeInfo<V, E>> mst();

    //最短路径
    //public abstract Map<V, E> shortestPath1(V begin);
    public abstract Map<V, PathInfo<V, E>> shortestPath(V begin); // 单源
    public abstract Map<V, Map<V, PathInfo<V, E>>> shortestPaths(); // 多源

    //访问器：有外面提供定义的节点访问
    public interface VertexVisitor<V> {
        boolean visit(V v);
    }
    //权值管理器：有外面提供对权值的比较、加法处理
    public interface WeightManager<E> {
        int compare(E w1, E w2);
        E add(E w1, E w2);
        E zero();
    }
    //提供外面访问的边的信息
    public static class EdgeInfo<V, E>{
        private V from;
        private V to;
        private E weight;
        protected EdgeInfo(V from, V to, E weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }
        public V getFrom() {
            return from;
        }
        public void setFrom(V from) {
            this.from = from;
        }
        public V getTo() {
            return to;
        }
        public void setTo(V to) {
            this.to = to;
        }
        public E getWeight() {
            return weight;
        }
        public void setWeight(E weight) {
            this.weight = weight;
        }
        @Override
        public String toString() {
            return "EdgeInfo{" +
                    "from=" + from +
                    ", to=" + to +
                    ", weight=" + weight +
                    '}';
        }
    }
    public static class PathInfo<V, E>{
        protected E weight;
        protected List<EdgeInfo<V, E>> edgeInfos = new LinkedList<>();
        public PathInfo() {}
        public PathInfo(E weight) {
            this.weight = weight;
        }
        public E getWeight() {
            return weight;
        }
        public void setWeight(E weight) {
            this.weight = weight;
        }
        public List<EdgeInfo<V, E>> getEdgeInfos() {
            return edgeInfos;
        }
        public void setEdgeInfos(List<EdgeInfo<V, E>> edgeInfos) {
            this.edgeInfos = edgeInfos;
        }

        @Override
        public String toString() {
            return "PathInfo{" +
                    "weight=" + weight +
                    ", edgeInfos=" + edgeInfos +
                    '}';
        }
    }
}
